package hot.hash;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class A128 {
//排序
    public int longestConsecutive1(int[] nums) {
        if(nums.length==0)return 0;
        Arrays.sort(nums);
        int len=1;
        int max=nums[0];
        int res=1;

     for(int i=1;i<nums.length;i++){
         if(nums[i]==max)continue;
         //如果当前数等于上一个数加1，长度加1
         if(nums[i]==max+1) {
             len++;
         }
         //不然，断掉了
         else{
             res=Math.max(res,len);
             len=1;
         }
         max=nums[i];
     }
     res=Math.max(res,len);
     return res;
    }
    //哈希表，使得时间复杂度缩短为O（n）
    public int longestConsecutive(int[] nums) {
        int res = 0;
        Set<Integer> st=new HashSet<>();
        for (int num : nums) {
            st.add(num);
        }
        for (Integer i : st) {
            if(st.contains(i-1))continue;//不是某段连续序列起点
            int y=i+1;
            while(st.contains(y)){
                y++;
            }
            res=Math.max(y-i+1,res);
        }
        return res;
    }
}
